package com.itheima.leetcode.od.b.linkedlist;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * (A卷,100分)- 单向链表中间节点（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 求单向链表中间的节点值，如果奇数个节点取中间，偶数个取偏右边的那个值。
 * <p>
 * 输入描述
 * <p>
 * 第一行 链表头节点地址 后续输入的节点数n
 * <p>
 * 后续输入每行表示一个节点，格式 节点地址 节点值 下一个节点地址(-1表示空指针)
 * <p>
 * 输入保证链表不会出现环，并且可能存在一些节点不属于链表。
 * <p>
 * 输出描述
 * <p>
 * 单向链表中间的节点值
 * <p>
 * 用例
 * <p>
 * 输入	00010 4
 * 00000 3 -1
 * 00010 5 12309
 * 11451 6 00000
 * 12309 7 11451
 * 输出	6
 * 说明	无
 * <p>
 * 输入	10000 3
 * 76892 7 12309
 * 12309 5 -1
 * 10000 1 76892
 * 输出	7
 * 说明	无
 */
public class UnidirectionalLinkedListIntermediateNode {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String head = sc.next();
        int n = sc.nextInt();

        HashMap<String, String[]> nodes = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String addr = sc.next();
            String val = sc.next();
            String nextAddr = sc.next();
            nodes.put(addr, new String[] {val, nextAddr});
        }*/

        HashMap<String, String[]> nodes = new HashMap<>();
        nodes.put("00000", new String[]{"3", "-1"});
        nodes.put("00010", new String[]{"5", "12309"});
        nodes.put("11451", new String[]{"6", "00000"});
        nodes.put("12309", new String[]{"7", "11451"});
        System.out.println(getResult("00010", nodes));
    }

    public static String getResult(String head, HashMap<String, String[]> nodes) {
        //    LinkedList<String> link = new LinkedList<>();
        ArrayList<String> link = new ArrayList<>();

        String[] node = nodes.get(head);
        while (node != null) {
            String val = node[0];
            String next = node[1];

            link.add(val);
            node = nodes.get(next);
        }

        int len = link.size();
        int mid = len / 2;
        return link.get(mid);
    }
}
